#include <stdio.h>
#include <stdlib.h>

#define True 1
#define False 0

/*function declerations will go here:*/
int letters_verification(char srting[256]);
int strlen(char string[], int pointer);
int power(int num, int index);
int strcmp(char stringA[], char stringB[], int pointer);

int is_firstime(int firstime[]);
int xor(int a, int b);
int bin2dec(int binary[], int length,int index);
void xorArraysIntoFirstArray(int binaryA[], int binaryB[], int length, int index);
int subStrCmp(char bigString[], char smallString[], int start, int end, int index);
void take_a_byte(int arr[],int location);
int only_numbers(char arr[],int i);
void mainmenu();
int getmatrix(int arr[18][18],int rows,int columns,int i, int j);
void print_moves(int moves[], int i, int column_end, int row_end);
int matrix_sum(int arr[18][18],int rows,int columns,int i,int j,int column_start,int row_start,int row_end,int column_end);
int matrix_sum_helper(int arr[18][18],int rows,int columns,int i,int j,int column_start,int row_start,int row_end,int column_end,int moves[],int k);
void switcharr(int st_int[],char st_char[],int i);
void intoarray(int kellet, int pellet[], int loc);
int inputcheck_4(int row,int column,int start_row,int start_column,int end_row,int end_column);

int iBinaryXor(int iFirstNumber[], int iSecondNumber[], int iLength);
int iMergeStrings(char str1[], int index1,char str2[],int index2, char result[], int index3);
int iFindWord(char sArr[], char sWord[],int iLength[1], int iArrIndex,int iWordIndex);

int main()
{
	/*
	//checking iMergeStrings
	char result[255];
	//First should return true
	if(iMergeStrings("abc",0,"bc",0,result,0)) printf("True\n");
	//Second should return false
	if(!iMergeStrings("dbc",0,"bc",0,result,0)) printf("False\n");
	puts(result);
	*/

	printf("Welcome to Homework 4!\n\n");
	mainmenu();
	getchar();
}
void intoarray(int kellet, int pellet[],int loc)
{
	if(!loc) return;	
	pellet[loc-1]=kellet%10;
	intoarray(kellet/10,pellet,loc-1);

}
int strlen(char string[], int pointer){
	if(string[pointer]=='\0') return pointer; 
	return strlen(string, pointer+1);
}
int power(int num, int index){
	if(index==0) return 1;
	return power(num,index-1)*num;
}
int strcmp(char stringA[], char stringB[], int pointer){
	if(stringA[pointer]!=stringB[pointer]) return False;
	if(stringA[pointer]=='\0') return True;
	return strcmp(stringA, stringB, pointer+1);
}

/*Here will come some auxilary functions, that are not library functions*/

int xor(int a, int b){
	return (a+b)%2;
}
int bin2dec(int binary[], int length,int index){
	if(index==length) return (binary[length-index] * power(2,index));
	return (bin2dec(binary,length, index+1) + (binary[length-index] * power(2,index)));
}
void xorArraysIntoFirstArray(int binaryA[], int binaryB[], int length, int index){
	if(index<=length){
		binaryA[index]=xor( binaryA[index], binaryB[index]);
		xorArraysIntoFirstArray(binaryA, binaryB, length, index+1);
	}
}

int subStrCmp(char bigString[], char smallString[], int start, int end, int index){
	if(bigString[start+index]!=smallString[index]) return False;
	if((bigString[start+index]=='\0')&&(smallString[index]=='\0')) return True;
	else return subStrCmp(bigString, smallString, start, end, index+1);
}

int iBinaryXor(int iFirstNumber[], int iSecondNumber[], int iLength)
{
	xorArraysIntoFirstArray(iFirstNumber, iSecondNumber, iLength, 0);
	return bin2dec(iFirstNumber, iLength, 0);
}

int iFindWord(char sArr[], char sWord[],int iLength[1], int iArrIndex,int iWordIndex)
{

	//again, lets break it down.
	
	//first i'll copy your first test, whether the long array is shorter than the short one...
	if ((sArr[iArrIndex]=='\0')&&(sWord[iWordIndex]!='\0')) return False;
	
	//now if the word is complete we can exit safely...
	if(sWord[iWordIndex]=='\0'){
		iLength[0]=iArrIndex;
		return True;
	}

	//if the long array is complete, we can also exit safely.
	if(sArr[iArrIndex]=='\0') return False;

	//if its not, we have work to do
	//we have two possebilities, the one the current letters are equal,
	if(sArr[iArrIndex]==sWord[iWordIndex]) return iFindWord(sArr,sWord,iLength,iArrIndex+1,iWordIndex+1);
	//second, the current letters aren't equal.
	return iFindWord(sArr,sWord,iLength,iArrIndex+1,iWordIndex);

	//and we are done!

	/*
	//Checks whether the long string is shorter than the short string. nice. liked :)
	if ((sArr[iArrIndex]=='\0')&&(sWord[iWordIndex]!='\0')) return False;
	
	//Now you check if the short string is done... ok.
	if (sWord[iWordIndex]=='\0'){
		iLength[0]=iArrIndex-iLength[0]; //didn't understand this line...
		return True; //ok.
	}

	if ((sArr[iArrIndex]==sWord[iWordIndex])&&(iLength[0]==-1)) iLength[0]=iArrIndex;
	//nevermind the logic, without adding the return property you will have segmentation fault each
	//time over and over again.
	if (sArr[iArrIndex]==sWord[iWordIndex]) iFindWord(sArr,sWord,iLength,iArrIndex++,iWordIndex++);

	else iFindWord(sArr,sWord,iLength,iArrIndex++,iWordIndex);
	
	//You should not reach the following line.
	//Don't write "444" or something else. it is bad programming. and in tests you want to leave
	//good impression... :-/
	return False;
	*/
}

int iMergeStrings(char str1[], int index1,char str2[],int index2, char result[], int index3){
	//Lets break it down,
	//if both string indexes at the end, lets finish
	if((str1[index1]=='\0')&&(str2[index2]=='\0')){
		result[index3]='\0';
		return True;
	}
	
	//then let us check whether the character in hand are letters or something else.
	//in case they are not, return False and lets go home and rest a bit...
	//if(((str1[index1]>122)||(str1[index1]<97))||((str2[index2]>122)||(str2[index2]<97))) return False;

	//now let us check the strings are in ascending order.... (teach your lecturers english please...)
	//we need to check the following letter is either bigger in ascii values, or '\0'
	if((str1[index1]>str1[index1+1])&&(str1[index1+1]!='\0')) return False;
	if((str2[index2]>str2[index2+1])&&(str2[index2+1]!='\0')) return False;

	//now to the funny business...
	
	//we are left with three other options, 
	//first the letters are equal
	if(str1[index1]==str2[index2]){
		result[index3]=str1[index1];
		result[index3+1]=str2[index2];
		return iMergeStrings(str1, index1+1, str2, index2+1, result, index3+2);
	}
	if(!str2[index2]){
		result[index3]=str1[index1];
		return iMergeStrings(str1, index1+1, str2, index2, result, index3+1);}
	if(!str1[index1]){
		result[index3]=str2[index2];
		return iMergeStrings(str1, index1, str2, index2+1, result, index3+1);}
	//second the letters are different, first str1[index] is bigger:
	if((str1[index1]<str2[index2])){
		result[index3]=str1[index1];
		return iMergeStrings(str1, index1+1, str2, index2, result, index3+1);
	}
	//second the opposite:
	if((str2[index2]<str1[index1])){
		result[index3]=str2[index2];
		return iMergeStrings(str1, index1, str2, index2+1, result, index3+1);
	}
	
	//and we are done!
	//to avoid warnings for not returning a value at the end of a function, just add False return at the end
	//assert it wont reach this spot, otherwise we are in trouble...
	return False;

}


	
	/*
{
	if ((str1[index1]=='\0')&&(str2[index2]=='\0'))
	{
		result[index3]='\0';
		return index3;
	}
	else
		if ((str2[index2]<str1[index1])&&(str2[index2]!='\0'))
		{
			result[index3]=str2[index2];
			iMergeStrings(str1,index1,str2,index2++,result,index3++);
		}
		else 
			if ((str2[index2]<str1[index1])&&(str2[index2]=='\0')&&(str1[index1]!='\0'))
			{
				result[index3]=str1[index1];
				iMergeStrings(str1,index1++,str2,index2,result,index3++);
			}
			else if ((str2[index2]>str1[index1])&&(str1[index1]!='\0'))
			{
				result[index3]=str1[index1];
				iMergeStrings(str1,index1,str2,index2++,result,index3++);
			}
			else if ((str2[index2]>str1[index1])&&(str1[index1]=='\0')&&(str2[index2]!='\0'))
			{
				result[index3]=str2[index2];
				iMergeStrings(str1,index1++,str2,index2,result,index3++);
			}
			return 444;

}
*/
void take_a_byte(int arr[],int location)
{
	scanf("%1d",&arr[location-1]);
	location--;
	if(location)
		take_a_byte(arr,location);	
}

void mainmenu()

{
	int point,substringlength1[1],the_matrix[18][18]={0},length,menu,byte1[8]={-11},byte2[8]={-22},substringlength[1],row,column,start_row,start_column,end_row,end_column;
	char first[256]={'/0'},longy[256],shorty[256],string1[256],string2[256],mergedstring[256];
	printf("Please select the required operation:\n"
		"1. XOR\n"
		"2. Find a Word\n"
		"3. Merge Strings\n"
		"4. Shortest Path\n"
		"0. Exit The Program\n"
		"Enter your selection: ");
	scanf ("%d",&menu);
	switch (menu)
	{
	case 0:
		return;		
	case 1:
		{

			printf("\nYou choose to perform XOR!\n"
				"Please enter the Length of the Arrays - maximum 8: \n");
			scanf ("%d",&length);
			getchar();
			printf("Please enter the first Byte: ");
			take_a_byte(byte1,length);
			getchar();
			printf("Please enter the Second Byte: ");
			take_a_byte(byte2,length);
			getchar();
			printf("The XOR results is: %d\n\n",iBinaryXor(byte1,byte2,length-1));
			break;
		}
	case 2:
		{
			substringlength[0]=-1;
			printf("\nYou choose to Find a Word!\n");
			printf ("Please insert the Sentence (max 255 characters):\n");
			getchar();
			gets(longy);
			printf ("Please Enter the Word you are Searching (max 255 characters):\n");
			gets(shorty);
			if (!iFindWord(longy,shorty,substringlength,0,0))
				printf("The \"%s\" word was NOT found!\n",shorty);
			else
			{
				first[0]=shorty[0];
				iFindWord(longy,first,substringlength1,0,0);
				printf("The \"%s\" word was found!\nThe length of the sub-string is: %d\n",shorty,(substringlength[0]-substringlength1[0])+1);
				
			}
				break;
		}
	case 3:
		{

			printf("\nYou choose to Merge Strings!\n"
				"Please enter the first string: ");
			getchar();
			gets(string1);
			printf("Please enter the Second string: ");
			gets(string2);
			if (only_numbers(string1,0)&&only_numbers(string2,0)&&(strlen(string1,0)+strlen(string2,0))<=256)
			{
				iMergeStrings(string1,0,string2,0,mergedstring,0);
				printf("The strings were sucesfully merged!\nThe Result string is: %s\n",mergedstring);
			}
			else
				printf("The strings were not merged!\nPlease try again later!!%s\n",mergedstring);
			break;
			}
	case 4:
		{
			printf("You choose to Find the Shorthest Path!\n"
				"Please Enter The Number of Rows in Your Matrix: ");
			scanf("%d",&row);
			printf("Please Enter The Number of Columns in Your Matrix: ");
			scanf("%d",&column);
			printf("Please Enter The Starting Index in the following format: (row,column)\n");
			getchar();
			getchar();
			scanf("%d",&start_row);
			getchar();
			scanf("%d",&start_column);
			getchar();
			printf("Please Enter The Ending Index in the following format: (row,column)\n");
			getchar();
			getchar();
			scanf("%d",&end_row);
			getchar();
			scanf("%d",&end_column);
			getchar();

			if (inputcheck_4(row,column,start_row,start_column,end_row,end_column))	
			{
				printf("Please Insert the Distance Matrix %dx%d Parameters - Legal Entry from 0 to 100!\n",row,column);
				if (getmatrix(the_matrix,row,column,0,0))
					matrix_sum(the_matrix,row,column,start_row,start_column,19,19,end_row,end_column);
				else
					printf("The Distance Matrix Parameters are not valid!!\nPlease Retry From the beggining!!\n\n");
			}
			else
				printf("\nYou Entered Wrong Input Please Retry!!\n");

		}
	default:
		printf ("You Inserted a Wrong Choice!!\nThe Program will restart!");
	}
		mainmenu();
}
int inputcheck_4(int row,int column,int start_row,int start_column,int end_row,int end_column)
{
	if(row<19&&row>0&&column<19&&column>0&&start_row>-1&&start_row<end_row&&start_column>-1&&start_column<column&&end_row<row&&end_column>-1&&end_column<column)
		return True;
	return False;
}
int only_numbers(char arr[],int i)
{
	if (arr[i]=='\0')
		return True;
	if (arr[i]<'A' || arr[i]>'z')
		return False;
	return only_numbers(arr,i+1);
}
int getmatrix(int arr[18][18],int rows,int columns,int i, int j)//////////////////////
{
	scanf("%d",&arr[i][j]);
	if ((arr[i][j]<0)||(arr[i][j]>100))
		return False;
	if (!(i-rows+1)&&!(j-columns+1))
		return True;
	if (j<(columns-1))
		getmatrix(arr,rows,columns,i,j+1);
	else
		if (j==(columns-1))
			getmatrix(arr,rows,columns,i+1,0);
}
void print_moves(int moves[], int i, int column_end, int row_end)
{
	if (i*2==0)
		printf("(%d,%d)",moves[i*2], moves[i*2 + 1]);
	else
		printf("->(%d,%d)",moves[i*2], moves[i*2 + 1]);
	if ((moves[i*2] == column_end) && (moves[i*2 + 1] == row_end))
		return;
	print_moves(moves, i + 1, column_end, row_end);
}

int matrix_sum_helper(int arr[18][18],int rows,int columns,int i,int j,int column_start,int row_start,int row_end,int column_end,int moves[],int k)//op4
{
	int a=5000,b=5000,c=5000,d=5000,e=5000;

	moves[k*2] = i;
	moves[k*2 + 1] = j;

	if((i==row_end)&&(j==column_end))
		return arr[row_end][column_end];
	if((j+1)<columns&&(j+1)!=row_start)
		a=(arr[i][j]+matrix_sum_helper(arr,rows,columns,i,j+1,i,j,row_end,column_end,moves,k+1));
	if((i+1)<rows&&(i+1)!=column_start)
		c=(arr[i][j]+matrix_sum_helper(arr,rows,columns,i+1,j,i,j,row_end,column_end,moves,k+1));
	if((j-1)>=0&&(j-1)!=row_start)
		e=(arr[i][j]+matrix_sum_helper(arr,rows,columns,i,j-1,i,j,row_end,column_end,moves,k+1));
	if((i+1)<rows&&(j+1)<columns)
		b=(arr[i][j]+matrix_sum_helper(arr,rows,columns,i+1,j+1,i,j,row_end,column_end,moves,k+1));
	if((i+1)<rows&&(j-1)>=0)
		d=(arr[i][j]+matrix_sum_helper(arr,rows,columns,i+1,j-1,i,j,row_end,column_end,moves,k+1));

	if((a<=b)&&(a<=c)&&(a<=d)&&(a<=e))
		return arr[i][j]+matrix_sum_helper(arr,rows,columns,i,j+1,i,j,row_end,column_end,moves,k+1);
	if((b<=a)&&(b<=c)&&(b<=d)&&(b<=e))
		return arr[i][j]+matrix_sum_helper(arr,rows,columns,i+1,j+1,i,j,row_end,column_end,moves,k+1);
	if((c<=a)&&(c<=b)&&(c<=d)&&(c<=e))
		return arr[i][j]+matrix_sum_helper(arr,rows,columns,i+1,j,i,j,row_end,column_end,moves,k+1);
	if((d<=a)&&(d<=b)&&(d<=c)&&(d<=e))
		return arr[i][j]+matrix_sum_helper(arr,rows,columns,i+1,j-1,i,j,row_end,column_end,moves,k+1);
	else
		return arr[i][j]+matrix_sum_helper(arr,rows,columns,i,j-1,i,j,row_end,column_end,moves,k+1);
}


int matrix_sum(int arr[18][18],int rows,int columns,int i,int j,int column_start,int row_start,int row_end,int column_end)
{
	int moves[400],r = matrix_sum_helper(arr,rows,columns,i,j,column_start,row_start,row_end,column_end,moves,0);
	printf("\nThe Shortest Path Distance Is: %d",r);
	printf("\nThe Shortest Path Is:\n");
	print_moves(moves,0,row_end,column_end);
	return r;
}
